package 蓝桥真题.javab组省赛历年真题.填空题;

import java.util.Arrays;

public class 路径 {
	   final static int N=100000,M=2*N;
	   static int h[]=new int[N],e[]=new int[M],ne[]=new int[M],w[]=new int[M],ds[]=new int[N],idx;
	   static boolean inq[]=new boolean[N];
	   static int gcd(int a,int b){
		      return b>0?gcd(b,a%b):a;
	   }
	   static void add(int a,int b,int c){
		      e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
	   }
       public static void main(String[] args) {
		      Arrays.fill(h, -1);
		      int n=2021;
		      for(int i=1;i<=n;i++)
	 	    	  for(int j=i+1;j<=n;j++){
	 	    		  if(j-i<=21){
	 	    			  int c=(i*j)/gcd(i,j);
	 	    			  add(i,j,c);
	 	    			  add(j,i,c);
	 	    		  }
	 	    	  }
		      
		      Arrays.fill(ds,0x3f3f3f3f);
    	      int q[]=new int[N],hh=0,tt=-1;
    	      q[++tt]=1;
    	      ds[1]=0;
    	      inq[1]=true;
    	      while(hh<=tt){
    	    	   int t=q[hh++];
    	    	   inq[t]=false;
    	    	   for(int i=h[t];i!=-1;i=ne[i]){
    	    		   int j=e[i];
    	    		   if(ds[t]+w[i]<ds[j]){
    	    			   ds[j]=ds[t]+w[i];
    	    			   if(!inq[j]){
    	    				   q[++tt]=j;
    	    				   inq[j]=true;
    	    			   }
    	    		   }
    	    	   }
    	      }
    	      if(ds[n]==0x3f3f3f3f);
    	      else System.out.print( ds[n]);
	}
}
